package canPartition

import (
	"fmt"
	"sort"
)

// leetcode 416 分割等和子集

// 作为0-1背包的基础问题一定要学懂，（二维、转一维，上下顺序，dp意义，遍历元素选取）
/*
在我理解来：
首先，需要具备三种要素：
1.物品：多种物品，每种物品对应不同的要素
2.重量：对应物品，每种都有一个重量
3.背包体积：盛放多个物品之后的最大体积
然后目的是要求的是背包承受完全之后的最大价值，这个对应物品
意思是物品要有的要素有：编号、重量、价值。背包的要素有：总体积、总价值。
*/

func canPartition(nums []int) bool {
	num, ok := sum(nums)
	if !ok {
		fmt.Println(false)
		return false
	}
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	fmt.Println(nums)
	cur := 0
	for i := 0; i < len(nums); i++ {
		cur += nums[i]
		if cur == num {
			fmt.Println(true)
			return true
		}
	}
	fmt.Println(false)
	return false
}

func sum(nums []int) (int, bool) {
	total := 0
	for i := 0; i < len(nums); i++ {
		total += nums[i]
	}
	if total%2 != 0 {
		return 0, false
	} else {
		return total / 2, true
	}
}

func dpCanPartition(nums []int) bool {
	num, ok := sum(nums)
	if !ok {
		fmt.Println(false)
		return false
	}
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	fmt.Println(nums)
	// 使用01背包处理数据进行遍历所有物品能够实现一半的数量
	// 这个j的取值区间很大，不能只是取数组长度，要从一半总值开始
	dp := make([]int, num+1)
	defer fmt.Println(dp)
	for i := 0; i < len(nums); i++ {
		for j := num; j >= nums[i]; j-- {
			fmt.Println(dp)
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
			if dp[j] == num {
				fmt.Println(true)
				return true
			}
		}
	}
	fmt.Println(false)
	return false
}
